package 剑指offer.链表;

import java.util.Stack;

/**
 * 递归或者通过栈解决
 */
public class 第6题逆序打印链表 {

    static class List {
        public int val;
        public List next;

        public List(int val) {
            this.val = val;
        }
    }



    public static void printList(List head) {
        if (head.next != null) {
            printList(head.next);
        }
        System.out.println(head.val);
    }

    public static void main(String[] args) {
        List l1 = new List(1);
        List l2 = new List(2);
        List l3 = new List(3);
        List l4 = new List(4);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;

//        printList(l1);
        Stack<Integer> stack = new Stack<>();
        printUseStack(l1, stack);
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 使用栈实现，防止递归太深溢出
     * @param head
     * @param stack
     */
    public static void printUseStack(List head, Stack<Integer> stack) {
        if (head != null) {
            stack.add(head.val);
            printUseStack(head.next, stack);
        }
    }
}
